package algo;

import java.util.LinkedList;
import java.util.Queue;

public class SoccerMaze {
    int m, n;
    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
        m = maze.length;
        n = maze[0].length;
        int[] went = new int[m * n];
        int[] dx = new int[]{1, 0, -1, 0};
        int[] dy = new int[]{0, 1, 0, -1};
        int dest = getIndex(destination[0], destination[1]);

        Queue<int[]> queue = new LinkedList<>();
        queue.offer(start);
        while (!queue.isEmpty()) {
            int[] stop = queue.poll();
            int x = stop[0];
            int y = stop[1];
            went[getIndex(x, y)] = 1;//已经访问过
            // System.out.println(x+" "+y + " accessed.");

            for (int i = 0; i <= 3; i++) {
                int nextx = x;
                int nexty = y;
                while (nextx + dx[i] >= 0 && nextx + dx[i] < m && nexty + dy[i] < n && nexty + dy[i] >= 0) {
                    if (maze[nextx + dx[i]][nexty + dy[i]] == 0) {
                        nextx += dx[i];
                        nexty += dy[i];
                    } else {
                        break;
                    }
                }
                int stay = getIndex(nextx, nexty);
                if (stay == dest) return true;
                if (went[stay] != 1) {
                    queue.offer(new int[]{nextx, nexty});
                    // System.out.println(nextx+" "+nexty + " in queue.");
                }
            }
        }
        return false;
    }

    private int getIndex(int x, int y) {
        return n * x + y;
    }
}
